#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <strings.h>

#include "hash.h"

/*
 * hash - the famous ELF Hash Function, used to hash a given string
 *
 * @str the string to be hashed
 *
 * return the hash value of the @str
 */
static int hash(char *str)
{
  unsigned int h = 0, g;
  
  while (*str) {
    h = (h << 4) + *str++;
    if ((g = (h & 0xF0000000))) {
      h ^= g >> 24;
    }
    h &= ~g;
  }

  return h;
}

/*
 * init_hash_table - initialize a hash table
 *
 * @size size of the hash table, adviced to be a prime
 *
 * return the hash table, or %NULL on error
 */
hash_table_t *init_hash_table(int size)
{
  hash_table_t *ht;

  assert(size > 0);

  ht = malloc(sizeof(hash_table_t));
  if (ht == NULL) {
    perror("malloc");
    return NULL;
  }

  ht->size  = size;
  ht->table = malloc(sizeof(hash_t *) * size);
  if (ht->table == NULL) {
    perror("malloc");
    free(ht);
    return NULL;
  }
  bzero(ht->table, ht->size);
  
  return ht;
}

/*
 * fini_hash_table - deinitialize desired hash table
 *
 * @ht the hash table will be deinitialized
 *
 * no return value
 */
void fini_hash_table(hash_table_t *ht)
{
  assert(ht && ht->table);
  
  free(ht->table);
  free(ht);
}

/*
 * hash_table_add - add a hash item to hash table
 *
 * @ht the hash table
 * @hi the hash item, hi->key should be pre-initialized
 *
 * return the hash item @hi
 */
hash_t *hash_table_add(hash_table_t *ht, hash_t *hi)
{
  assert(ht && hi && ht->size && ht->table && hi->key);

  hi->hash = hash(hi->key)%ht->size;
  hi->next = ht->table[hi->hash];
  ht->table[hi->hash] = hi;

  return hi;
}

/*
 * hash_table_del - delete a hash item from a hash table
 *
 * @ht the hash table
 * @hi the hash item
 *
 * return deleted hash item from the table, %NULL if no such item
 */
hash_t *hash_table_del(hash_table_t *ht, char *key)
{
  int hkey;
  hash_t *hi, *rv=NULL;

  assert(ht && ht->size && ht->table && key);

  hkey = hash(key)%ht->size;
  hi = ht->table[hkey];

  /* no such key in hash table */
  if (hi == NULL) {
    return NULL;
  }

  if (strcmp(key, hi->key) == 0) {
    ht->table[hkey] = hi->next;
    return hi;
  }

  for (;hi->next; hi = hi->next) {
    if (strcmp(key, hi->next->key) == 0) {
      rv = hi->next;
      hi->next = hi->next->next;
    }
  }

  return rv;
}

/*
 * hash_table_index - search the hash table with desired key
 *
 * @ht  the hash table
 * @key the hash key string
 *
 * return hash item match the key, %NULL if no match item exist
 */
hash_t *hash_table_index(hash_table_t *ht, char *key)
{
  hash_t *hi;

  assert(ht && ht->size && ht->table && key);

  for (hi=ht->table[hash(key)%ht->size]; hi; hi = hi->next) {
    if (strcmp(key, hi->key) == 0) {
      return hi;
    }
  }

  return NULL;
}
